Linear systems of equations are associated with many problems in engineering and science, as well as with applications of mathematics to the social sciences and economic problems. A linear system can be represented by the set of equations: ##EQU1##
A linear system is often replaced by a matrix, which contains all the information necessary to determine a solution, but in a compact form. A matrix is a rectangular array of elements with end rows and end columns in which not only is the value of an element important, but also its position in the array. A notation for an n.times.m (n by m) matrix is a capital letter such as A for the entire matrix and a lower case letter with double subscripts, such as a.sub.ij, to refer to the entry at the intersection for the ith row and jth column. For example, a matrix representing the coefficients of the above system of equations (1) would have the form: ##EQU2##
The entire linear system given by (1) can be represented by a matrix and two vectors: ##EQU3## In equation (3), the columns x.sub.i and b.sub.i represent the two vectors.
Broadly speaking, there are two different classes of techniques for solving linear systems of equations: direct techniques and iterative techniques. Direct techniques are methods that give an answer in a fixed number of steps, subject only to round off errors created by the limits of precision in digital computers. Iterative techniques for solving a linear system start with an initial approximation to the solution and generate a sequence of vectors that converge to the solution.
By representing a linear system of equations as a matrix, a direct technique called Gaussian elimination with backward substitution can be used to solve the system. Gaussian elimination is well known in the art and further details can be found in "Numerical Analysis", R. Burden & D. Faires, Fifth Edition, PWS Publishing Co., 1993, P. 324-331. Typically, a computer algorithm for executing Gaussian elimination is slow, especially with matrices of large dimensions.
Iterative techniques involve a process that converts a system of equations Ax=b, where A represents a matrix and b and x represent vectors (see above equation (3)), into an equivalent system having the form x=Tx+c for some matrix T and vectors c and x. After an initial vector x.sup.(0) is selected, the sequence of approximate solutions is recursively generated by computing: EQU x.sup.(k) =Tx.sup.(k-1) +c, for each k=1,2,3, (4)
In Equation (4), x.sup.(k) represents an approximate solution corresponding to the kth iteration, while x.sup.(k-1) represents the approximate solution generated by the prior iteration.
Iterative techniques are seldom used for solving linear systems of small dimensions, since the time required for sufficient accuracy exceeds that required for direct techniques such as the Gaussian elimination method. For large systems with a high percentage of zero entries, however, these techniques are relatively efficient in terms of both computer storage and computational time. Systems of this type arise frequently in circuit analysis and in the numerical solution of boundary value problems and partial differential equations. Using an iterative technique to solve linear systems requires large amounts of computational time. However, in many applications, such as systems with a low percentage of zero entries, conventional computer technology does not provide sufficient performance in terms of speed. There is thus a need for a computer-based approach of solving linear systems that is computationally efficient and fast.